import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    final private int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int numEnclaves(int[][] grid) {
        int h = grid.length;
        int w = grid[0].length;
        boolean[][] visited = new boolean[h][w];
        int countCanLeave = 0;

        for (int r = 0; r < h; r++) {
            for (int c : new int[]{0, w - 1}) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    countCanLeave += bfs(grid, r, c, visited);
                }
            }
        }
        for (int c = 1; c < w - 1; c++) {
            for (int r : new int[]{0, h - 1}) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    countCanLeave += bfs(grid, r, c, visited);
                }
            }
        }

        int countLand = 0;
        for (int[] row : grid) {
            for (int v : row) {
                if (v == 1) {
                    countLand++;
                }
            }
        }

        return countLand - countCanLeave;
    }

    private boolean inBounds(int[][] grid, int r, int c) {
        int h = grid.length;
        int w = grid[0].length;
        return r >= 0 && r < h && c >= 0 && c < w;
    }

    private int dfs(int[][] grid, int r, int c, boolean[][] visited) {
        visited[r][c] = true;
        int area = 1;
        for (int[] dir : DIR) {
            int nextR = r + dir[0];
            int nextC = c + dir[1];

            if (inBounds(grid, nextR, nextC) && grid[nextR][nextC] == 1 && !visited[nextR][nextC]) {
                area += dfs(grid, nextR, nextC, visited);
            }
        }
        return area;
    }

    private int bfs(int[][] grid, int r, int c, boolean[][] visited) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        int area = 0;
        while (!queue.isEmpty()) {
            int[] item = queue.poll();
            r = item[0];
            c = item[1];
            area += 1;
            for (int[] dir : DIR) {
                int nextR = r + dir[0];
                int nextC = c + dir[1];
                if (inBounds(grid, nextR, nextC) && grid[nextR][nextC] == 1 && !visited[nextR][nextC]) {
                    queue.offer(new int[]{nextR, nextC});
                    visited[nextR][nextC] = true;
                }
            }
        }
        return area;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
